def binary_search(lst, target):
    """
    在数组中找到并返回索引，没有则返回-1
    :param num:
    :param lst:
    :return:
    """
    if not lst:
        return -1

    l = 0
    r = len(lst) - 1
    while l <= r:
        # mid = (l + r)/2 可能会发生溢出
        mid = l + ((r - l) >> 1)
        if lst[mid] < target:
            l = mid + 1
        elif lst[mid] > target:
            r = mid - 1
        else:
            return mid

    return -1


def binary_search_moban(num, lst):
    """
    二分模板，来自B站 BV1d54y1q7k7. 按要求返回 l or r
    :param num:
    :param lst:
    :return:
    """
    if not lst:
        return -1

    l = -1
    r = len(lst)
    while l + 1 != r:
        mid = l + ((r - l) >> 1)
        if lst[mid] < num:
            l = mid
        else:
            r = mid

    return r


if __name__ == "__main__":
    lst = [1, 2, 3, 4, 5, 7, 9]
    print(binary_search(lst, 4))
